#include <iostream>
#include <vector>
#include <algorithm>
#include "conio.h"

using namespace std;

void merge(vector<int> &arr, int l, int median, int r)
{
	vector<int> res(r-l+1);
	int i1 = l, i2 = median+1, 
		i_res = 0;

	while (i1 <= median && i2 <= r)
	{
		if (arr[i1] < arr[i2])
		{
			res[i_res] = arr[i1];
			++i1;
		}
		else
		{
			res[i_res] = arr[i2];
			++i2;
		}
		++i_res;
	}

	while (i1 <= median)
		res[i_res++] = arr[i1++];

	while (i2 <= r)
		res[i_res++] = arr[i2++];

	for (int i = l; i <= r; ++i)
		arr[i] = res[i-l];
}

void merge_sort_rec(vector<int> &arr, int l, int r)
{
	if (l >= r)
		return;

	int median = (l+r)/2;
	merge_sort_rec(arr, l, median);
	merge_sort_rec(arr, median+1, r);
	merge(arr, l, median, r);
}

vector<int> merge_sort(const vector<int> &arr)
{
	vector<int> res = arr;
	merge_sort_rec(res, 0, res.size()-1);
	return res;
}

void main()
{
	int n_elems;
	cout << "Input number of elements:" << endl;
	cin >> n_elems;

	cout << "Input elements:" << endl;
	vector<int> arr(n_elems);
	for (int i = 0; i < n_elems; ++i)
		cin >> arr[i];

	vector<int> res = merge_sort(arr);
	
	cout << "Sorted array:" << endl;
	for (int i = 0; i < res.size(); ++i)
		cout << res[i] << " ";
	_getch();
}